#include <bits/stdc++.h>
using namespace std;

class Test{
public:
	// 双指针法做四数之和
	vector<vector<int>> fourSum(vector<int>& nums, int target) {
		vector<vector<int>> result;
		// 1. 排序
		sort(nums.begin(),nums.end());
		for(int k = 0;k < nums.size();k++){
			// 2. 剪枝
			if(nums[k] > target && nums[k] > 0 && target > 0){
				break;
			}
			// 3. 去重
			if(k > 0 && nums[k] == nums[k-1]) continue;
			for(int i = k + 1;i < nums.size();i++){
				// 4. 对i剪枝
				if(nums[k]+nums[i] > target &&
					nums[k]+nums[i] > 0 &&
					target > 0){
					break;
				}
				// 5. 对i去重
				if(i > k+1 && nums[i] == nums[i-1]) continue;
				int left = i + 1;
				int right = nums.size()-1;
				while(left < right){
					long tmp = (long)nums[k] + nums[i] + nums[left] + nums[right];
					if(tmp > target){
						right--;
					}else if(tmp < target){
						left++;
					}else{
						result.push_back({nums[k] , nums[i] , nums[left] , nums[right]});
						while(left < right && nums[left] == nums[left+1]) left++;
						while(left < right && nums[right] == nums[right-1]) right--;
						left++;
						right--;
					}
				}
			}
		}
		return result;
	}
};


int main(){
	
	return 0;
}
